package com.leecode;

import lombok.val;

public class Leet279 {
	public static void main(String[] args) {
//		System.out.println(Math.sqrt(5));//2.23...
		System.out.println(new Leet279().numSquares(12));
	}
	int count=0;
	public int numSquares(int n) {
		return Math.min(test(n),test2(n));
	}
	public int test(int n){
		if(n<=3)return count+=n;

		double sqrt = Math.sqrt(n);
		int sqrtInt = (int)Math.floor(sqrt);
		if (sqrt != sqrtInt) {
			count++;
			return test(n - sqrtInt*sqrtInt);
		}else{
			return count+1;
		}
	}
	public int test2(int n) {
		if(n<=3)return count+=n;

		double sqrt = Math.sqrt(n);
		int sqrtInt = (int)Math.floor(sqrt);
		for(int a=sqrtInt;a>=1;a--){
			if(n%(a*a)==0){
				return n / (a * a);
			}
		}

		return n;
	}
}
